package com.test.daily.leetcode.y2022.m05.day0526.v04;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/26 下午 10:57
 * @version: 1.0
 */
public class Solution {

    public static class Node<V> {
        public V v;

        public Node(V v) {
            this.v = v;
        }
    }

    public static class UnionFind<V> {
        public HashMap<Node<V>, Integer> sizeMap;
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parentMap;
        int sets;

        public UnionFind(List<V> list) {
            int N = list.size();
            sets = N;
            for (int i = 0; i < list.size(); i++) {
                Node<V> node = new Node<>(list.get(i));
                sizeMap.put(node, 1);
                parentMap.put(node, node);
                nodes.put(list.get(i), node);
            }
        }

        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> stack = new Stack<>();
            while (cur != parentMap.get(cur)) {
                stack.push(cur);
                cur = parentMap.get(cur);
            }
            while (!stack.isEmpty()) {
                parentMap.put(stack.pop(), cur);
            }
            return cur;
        }

        public void union(Node<V> a, Node<V> b) {
            Node<V> aFather = findFather(a);
            Node<V> bFather = findFather(b);
            if (aFather != bFather) {
                Node<V> small = sizeMap.get(aFather) >= sizeMap.get(bFather) ? aFather : bFather;
                Node<V> big = small == aFather ? bFather : aFather;
                parentMap.put(small, big);
                sizeMap.put(big, sizeMap.get(small) + sizeMap.get(big));
                sizeMap.remove(small);
            }
        }
        public int sets(){
            return sizeMap.size();
        }
    }
}
